#include <algorithm>
#include <vector>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <climits>
#include <cstdin>

struct Building
{
	std::int64_t left, right, height;
};

class Solution
{
public:
	std::vector<std::pair<int, int>> getSkyline(std::vector<std::vector<int>>& buildings)
	{
		std::vector<Building> builds(buildings.size());
		std::transform(buildings.cbegin(), buildings.cend(), builds.begin(), [](const std::vector<int>& b) { return Building{ b[0], b[1], b[2] }; });
		
		std::unordered_set<std::int64_t> criticalSet;
		for (auto& b : builds) {
			criticalSet.insert(b.left);
			criticalSet.insert(b.right);
		}
		std::vector<std::int64_t> critical(criticalSet.size());
		std::copy(criticalSet.cbegin(), criticalSet.cend(), critical.begin());
		std::sort(critical.begin(), critical.end());

		std::unordered_map<std::int64_t, std::unordered_set<Building*>> bMap;
		for (auto& b : builds) {
			bMap[b.left].insert(&b);
			bMap[b.right].insert(&b);
		}
		
		std::vector<std::pair<int, int>> points;
		std::unordered_set<Building*> bSet;
		for (auto p : critical) {
			for (auto b : bMap[p]) {
				if (bSet.count(b)) bSet.erase(b);
				else bSet.insert(b);
			}
			auto height = std::numeric_limits<std::int64_t>::min();
			for (auto b : bSet) height = std::max(height, b->height);
			if (points.empty() || height!=points.back().second) points.emplace_back(p, height);
		}

		return points;
	}
};